package com.clstu.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * leetCode 1094拼车
 */
class Solution3 {

    public static void main(String[] args) {
        //测试
        int[][] trips = {{2,1,5},{3,5,7}};
        int capacity = 3;
        System.out.println(carPooling(trips,capacity));
    }

    public static boolean carPooling(int[][] trips, int capacity) {
        //思路,准备两个堆,一个按照上车时间排序,一个按照下车时间排序
        //先全部进入到上车的堆里,如果上车,就弹出加入到下车的堆里
        //最后如果全部都可以上次,返回true,否则返回false
        PriorityQueue<int[]> ins = new PriorityQueue<int[]>(new InComparator());
        PriorityQueue<int[]> outs = new PriorityQueue<>(new OutComparator());
        //先全部都加入到上车堆中
        for(int i=0;i<trips.length;i++){
            ins.add(trips[i]);
        }
        int remainder = capacity;
        int cur = 0;
        for(int i=0;i< trips.length;i++){
            //从上次堆中取数据
            int[] in = ins.poll();
            //更新时间
            System.out.println(Arrays.toString(in));
            cur = in[1];
            //先下车,再上车
            //下车
            if(!outs.isEmpty()){
                while (outs.peek()[2]<=cur){
                    remainder+=(outs.poll())[0];
                    if(outs.isEmpty()) break;
                }
            }
            //上车
            remainder-=in[0];
            //如果位置不够
            System.out.println(remainder);
            if(remainder<0) return false;
            outs.add(in);
//            System.out.println(outs);
        }
        //如果全员上车,返回true
        return ins.isEmpty();
    }

    //比较器
    public static class OutComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[2] - o2[2];
        }
    }

    //上车时间比较器
    public static class InComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    }
}
